package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//47. 全排列 II
//
//
//给定一个可包含重复数字的序列，返回所有不重复的全排列。
//
//示例:
//
//输入: [1,1,2]
//输出:
//[
//  [1,1,2],
//  [1,2,1],
//  [2,1,1]
//]



public class Solution047 {
	public List<List<Integer>> permuteUnique(int[] nums) {
		
		if (nums == null || nums.length == 0) {
			return new ArrayList<List<Integer>>();
		}
		
		Arrays.sort(nums);
		
		List<List<Integer>> res = permute(nums, 0);
		return res;
    }
	
	
	private List<List<Integer>> permute(int[] nums, int start) {
		
		List<List<Integer>> res = new ArrayList<>();
		
		Set<Integer> begindata = new HashSet<>();
		
		if (start == nums.length - 1) {
			List<Integer> list = new ArrayList<>();
			list.add(nums[start]);
			res.add(list);
			return res; 
		}
		
		for (int i=start; i<nums.length; i++) {
			
			if (begindata.contains(nums[i])) {
				continue;
			}
			begindata.add(nums[i]);
			
			swap(nums, start, i);
			
			List<List<Integer>> sub = permute(nums, start + 1);
			
			for (List<Integer> list : sub) {
				list.add(0, nums[start]);
				res.add(list);
			}
			
			swap(nums, start, i);
		}
		
		return res;
	}
	
	private void swap(int[] nums, int i, int j) {
		int t = nums[i];
		nums[i] = nums[j];
		nums[j] = t;
	}
	
	
	public static void main(String[] args) {
		new Solution047().permuteUnique(new int[]{0,1,0,0, 9});
	}
}